package com.链表;

/**
 * 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
 *
 * 如果有两个中间结点，则返回第二个中间结点。
 */
public class 链表的中间结点 {
    static class Solution {
        public ListNode middleNode(ListNode head) {
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode slow = dummy,fast = dummy;
            /**
             * 快慢指针，慢指针每次走一步，快指针每次走两步，当快走完时，就到了中间
             */
            while ( fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            /**
             * 当为偶数时 快指针的下一个为空，慢指针取下一个
             *  当为奇数时，当前快指针为空，取当前慢指针
             */
            if(fast==null){
                return slow;
            }
            else{
                return slow.next;
            }

        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(new int[]{1});
        Solution solution = new Solution();
        System.out.println( solution.middleNode(head));
    }

}
